package com.example.hot100;

import java.util.Arrays;

/**
 * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
 *  如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 *  必须 原地 修改，只允许使用额外常数空间。
 *
 *  示例 1：
 * 输入：nums = [1,2,3]
 * 输出：[1,3,2]
 *
 *  示例 2：
 * 输入：nums = [3,2,1]
 * 输出：[1,2,3]
 *
 *  示例 3：
 * 输入：nums = [1,1,5]
 * 输出：[1,5,1]
 *
 *  示例 4：
 * 输入：nums = [1]
 * 输出：[1]
 */
public class Leetcode31_NextPermutation {
    public static void main(String[] args) {
        int[] nums = {1, 1, 5};
        nums = new int[] {1, 2, 3, 8, 5, 7, 6, 4};
//        nums = new int[] {1, 5, 8, 4, 7, 6, 5, 3, 1};
        new Solution().nextPermutation(nums);

        System.out.println(Arrays.toString(nums));
    }

    static class Solution {

        private void nextPermutation1(int[] nums) {
            int p1 = nums.length - 2, p2 = nums.length - 1;
            // 从后向前遍历，寻找第一个非降序的位置
            while (p1 >= 0 && nums[p1] >= nums[p1 + 1]) {
                --p1;
            }

            if (p1 >= 0) {
                // 从后向前遍历寻找到第一个比nums[p1]大的
                while (p2 >= 0 && nums[p2] <= nums[p1]) {
                    --p2;
                }

                // 交换两个数
                swap(nums, p1, p2);
            }
            // 将p1 + 1 到 最后的所有数字进行翻转
            reverse(nums, p1 + 1, nums.length - 1);
        }

        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }

        private void reverse(int[] nums, int start, int end) {
            while (start < end) {
                int tmp = nums[start];
                nums[start] = nums[end];
                nums[end] = tmp;
                ++start;
                --end;
            }
        }

        public void nextPermutation(int[] nums) {
            nextPermutation1(nums);
        }
    }
}
